#include <stdlib.h>
#include "UF.h"

/**
 * Program 4.8 Equivalence-relations ADT implementation
 * ----------------------------------------------------
 * 加权快速合并算法
 * 
 */

static int *id;
static int *sz; 


void UFinit(int N){
    int i;
    id = malloc(N * sizeof(int));
    sz = malloc(N * sizeof(int));

    for(i = 0; i < N; i++){
        id[i] = i;
        sz[i] = 1;
    }
}

static int find(int p){
    int i;
    for (i = p; i != id[i]; i = id[i]) {
        ;
    }
    return i;
}

int UFfind(int p, int q){
    return find(p) == find(q);
}

void UFunion(int p, int q){
    int i = find(p);
    int j = find(q);
    if (sz[i] < sz[j]) {
        id[i] = j;
        sz[j] += sz[i];
    }else {
        id[j] = i;
        sz[i] += sz[j];
    }
}

